1. Field of Invention
This invention relates generally to digital data communication systems, particularly to the encoding and decoding of error correcting codes.
3. Related Art and Other Considerations
In a digital data communication system (including storage and retrieval from optical or magnetic media), error control systems are typically employed to increase the transfer rate of information and at the same time make the error rate arbitrarily low. For fixed signal-to-noise ratios and fixed bandwidths improvements can be made through the use of error-correcting codes.
With error-correction coding, the data to be transmitted or stored is processed to obtain additional data symbols (called check symbols or redundancy symbols). The data and check symbols together make up a codeword. After transmission or retrieval, the codeword is mathematically processed to obtain error syndromes which contain information about locations and values of errors.
The Reed-Solomon codes are a class of multiple-error correcting codes. One of the most popular methods of decoding is to generate the error locator polynomial .sigma.(x) [i.e the connection polynomial using the Berlekamp-Massey algorithm]; generate the error evaluator polynomial .omega.(x) from the error locator polynomial; perform a root search for the error locator polynomial to detect error locations; and then evaluate the error evaluator polynomial at the error locator polynomial root to calculate an error value.
Most logic circuits for error detection and correction implement the Berlekamp-Massey algorithm. Each iteration of the Berlekamp-Massey algorithm has two parts or stages: ##EQU1## As used herein, d.sub.n is a discrepancy number and .tau. is an intermediate polynomial used in calculating .sigma.. The choice of the two alternate expressions for .tau. depends on whether or not the .sigma.(x) update results in an increase in the order of .sigma.(x). When an increase results, .tau.(x) is set to .sigma.(x) and d.sub.r is set to d.sub.n. If .tau.(x) is instead set to d.sub.n.sup.-1 x.sigma.(x) then d.sub.r can be eliminated and the recursions become: ##EQU2## The second stage requires the result of the first stage. To minimize circuitry size it is desirable to perform all arithmetic in a serial manner and to make updates in a serial manner (as opposed to a parallel manner requiring space-consuming parallel buses). Assuming the field used is GF(2.sup.m), the minimum number of clock cycles needed for a serialized implementation is 2m clocks per iteration, i.e. m clocks per stage.
U.S. Pat. No. 4,845,713, issued Jul. 4, 1989 to Zook, shows a method which uses 2m+1 clocks per iteration and bit-serial multipliers and adders. However it uses 4t+1 m-bit registers and a 2.sup.m .times.m ROM look-up table for inversion (t being the number of correctable errors). Also, the update for .tau..sup.(n+1) (x) is done in a parallel manner.
Various decoding methods are described in Whiting's PhD dissertation for the California Institute of Technology entitled "Bit-Serial Reed-Solomon Decoders in VLSI," 1984. Whiting's preferred implementation uses the following modified set of recursion equations: ##EQU3## Whiting's implementation can perform an iteration in 2m clocks if a 2.sup.m .times.m ROM look-up table is used for inversion. The updates can be done serially, but d.sub.n.sup.-1 must be parallel bussed to each multiplier. Whiting's overall implementation would use 5(t+1) m-bit registers. The reason that the number of registers is proportional to t+1 instead of t is because .sigma..sub.0 is not identically equal to 1, i.e. the .sigma.(x) generated by EQUATIONS 2 is the .sigma.(x) generated by EQUATIONS 1 multiplied by some constant. Whiting also mentions using the following modified set of recursion equations: ##EQU4## Whiting's second method uses no inversions, but for serial updates it requires 6(t+1)+2 m-bit registers and d.sub.n and d.sub.r must be parallel bussed to each multiplier.
All known implementations for the Berlekamp-Massey algorithm use some combination of a 2.sup.m .times.m ROM, symbol-wide signal paths, and an excessive number of m-bit registers in order to perform an iteration in 2m clock cycles. An inherent problem with all of the above sets of iteration equations is that .sigma..sup.(n+1) (x) depends on .tau..sup.(n) (x) and, in turn, .tau..sup.(n+1) (x) depends on .sigma..sup.(n) (x) . Since one or both of them depend upon d.sub.n, consequentially d.sub.n must be calculated during the first m clock cycles and then .sigma..sup.(n+1) (x) and .tau..sup.(n+1) (x) must both be calculated during the second m clock cycles. This implies the need for temporary storage for one or both of .sigma..sup.(n) (x) and .tau..sup.(n) (x) when used in multiplications to produce .sigma..sup.(n+1) (x) or .tau..sup.(n+1) (x). Thus there is a need for a more efficient method.